package dp;

import org.junit.Test;

import java.util.Stack;

public class LongestValidParentheses32 {
    @Test
    public void test() {
        longestValidParentheses("()");
        longestValidParentheses("(()");
        longestValidParentheses(")(((((()())()()))()(()))(");
    }

    // 这种解法正确了, 根本不用dp. 括号配对有特殊性, 用栈就可以了
    public int longestValidParentheses(String s) {
        if (s == null || s.isEmpty()) {
            return 0;
        }
        char[] cs = s.toCharArray();
        Stack<CharIndex> stack = new Stack<>();
        int maxLength = 0;
        for (int i = 0; i < cs.length; i++) {
            char c = cs[i];
            if (c == '(') {
                stack.push(new CharIndex(c, i));
            } else { // c = ')'
                if (stack.size() > 0) {
                    CharIndex top = stack.peek();
                    if (top.c == '(') {
                        stack.pop();
                        if (stack.size() > 0) {
                            top = stack.peek();
                            maxLength = Math.max(maxLength, i - top.index);
                        } else {
                            maxLength = i + 1;
                        }
                    } else { // top.c = ')'
                        stack.push(new CharIndex(c, i));
                    }
                } else { // stack is empty
                    stack.push(new CharIndex(c, i));
                }
            }
        }
        System.out.format("s: %s, maxLength: %d\n", s, maxLength);
        return maxLength;
    }

    static class CharIndex {
        char c;
        int index;

        public CharIndex(char c, int index) {
            this.c = c;
            this.index = index;
        }
    }

    // 这个方法有问题, 结果不正确, 且复杂度高
    public int longestValidParentheses2(String s) {
        if (s == null || s.isEmpty()) {
            return 0;
        }
        char[] c = s.toCharArray();

        // range = [start, end), length = end - start.
        boolean[][] dp = new boolean[c.length+1][c.length+1];
        for (int i = 0; i <= c.length; i++) {
            dp[i][i] = true;
        }

        int maxLength = 0;
        for (int k = 2; k <= c.length; k += 2) {
            // 当range=[start, end)时, 要特别注意i的上界是小于等于.
            for (int i = 0; i <= c.length - k; i++) {
                int j = i + k;
                // i = 1, j = 3
                dp[i][j] = (dp[i][j-2] && c[j-2] == '(' && c[j-1] == ')') ||
                        (dp[i+2][j] && c[i] == '(' && c[i+1] == ')') ||
                        (dp[i+1][j-1] && c[i] == '(' && c[j-1] == ')');
                if (dp[i][j]) {
                    maxLength = k;
                }
            }
        }
        System.out.format("s: %s, maxLength: %d\n", s, maxLength);
        return maxLength;
    }
}
